#include <stdlib.h>
#include <stdio.h>

// 拓扑排序，

typedef char VertexType; // 顶点数据类型
typedef int EdgeType;  // 边的权值类型
#define MAXVEX 100       // 最大顶点数

typedef struct{
    VertexType vexs[MAXVEX];          // 顶点表
    EdgeType arc[MAXVEX][MAXVEX];     // 邻接矩阵
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} Graph;

typedef struct EdgeNode{
    int edge_vex;            // 该边所指向的顶点的位置
    struct EdgeNode *next;   // 指向下一条边的指针
} EdgeNode;

typedef struct VertexNode{
    VertexType data;         // 顶点信息
    int in;                 // 顶点入度
    EdgeNode *head;     // 指向第一条依附该顶点的边的指针
} VertexNode;

typedef VertexNode AdjList[MAXVEX];

typedef struct{
    AdjList adjList;     // 邻接表
    int numVertexes, numEdges;        // 图的当前顶点数和边数
} GraphAdjList;

typedef GraphAdjList *Adj_List_Graph;
int top = -1; // 栈顶指针
int stack[MAXVEX]; // 栈

// 判断栈是否为空
int isEmpty(){
    if (top == -1){
        return 1;
    }
    return 0;
}

// 入栈
void push(int i){
    if (top == MAXVEX - 1){
        printf("栈满");
        return;
    }
    stack[++top] = i;
}

// 出栈
int pop(){
    if (isEmpty()){
        printf("栈空");
        return -1;
    }
    return stack[top--];
}

void createGraph(Graph *G){
    G->numVertexes = 14;
    G->numEdges = 20;

    for (int i = 0; i < G->numVertexes; i++){   // 初始化邻接矩阵
        G->vexs[i] = i;
    }
    for (int i = 0; i < G->numVertexes; i++){      // 初始化邻接矩阵
        for (int j = 0; j < G->numVertexes; j++){  // 初始化邻接矩阵
            if (i == j){                  
                G->arc[i][j] = 0;  // 对角线为0
            }
        }
    }

    // 建立边
G->arc[0][4] = 1;
G->arc[0][5] = 1;
G->arc[0][11] = 1;
G->arc[1][2] = 1;
G->arc[1][4] = 1;
G->arc[1][8] = 1;
G->arc[2][5] = 1;
G->arc[2][6] = 1;
G->arc[2][9] = 1;
G->arc[3][2] = 1;
G->arc[3][13] = 1;
G->arc[4][7] = 1;
G->arc[5][8] = 1;
G->arc[5][12] = 1;
G->arc[6][5] = 1;
G->arc[8][7] = 1;
G->arc[9][10] = 1;
G->arc[9][11] = 1;
G->arc[10][13] = 1;
G->arc[12][9] = 1;
}

void createALGraph(Adj_List_Graph *GL, Graph G){
    EdgeNode *e;
    *GL = (Adj_List_Graph)malloc(sizeof(GraphAdjList));
    (*GL)->numVertexes = G.numVertexes;
    (*GL)->numEdges = G.numEdges;
    
    for (int i = 0; i < G.numVertexes; i++){ // 初始化邻接表
        (*GL)->adjList[i].data = G.vexs[i];
        (*GL)->adjList[i].in = 0; // 初始化入度为0
        (*GL)->adjList[i].head = NULL; // 初始化边表为空
    }

    for (int i = 0; i < G.numVertexes; i++){ // 建立边表
        for (int j = 0; j < G.numVertexes; j++){
            if (G.arc[i][j] == 1){ // 有边
                e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 创建边结点
                e->edge_vex = j; // 该边指向的顶点位置
                e->next = (*GL)->adjList[i].head; // 将e指向当前顶点的第一条边
                (*GL)->adjList[i].head = e; // 将当前顶点的第一条边指向e
                (*GL)->adjList[j].in++; // 被指向的顶点入度加1
            }
        }
    }
}

void topologicalSort(Adj_List_Graph GL){
    int count = 0; // 记录输出顶点的个数
    EdgeNode *p;
    for (int i = 0; i < GL->numVertexes; i++){ // 将所有入度为0的顶点入栈
        if (GL->adjList[i].in == 0){
            push(i);
        }
    }

    while (!isEmpty()){ // 栈不为空
        int j = pop(); // 出栈
        printf("V%d ->", GL->adjList[j].data); // 输出该顶点
        count++;
        p = GL->adjList[j].head; // p指向该顶点的第一条边
        while (p){ // 遍历该顶点的所有边
            int k = p->edge_vex; // k为该边指向的顶点位置
            GL->adjList[k].in--; // 被指向的顶点入度减1
            if (GL->adjList[k].in == 0){ // 如果入度为0,则入栈
                push(k);
            }
            p = p->next; // 指向下一条边
        }
    }
    if (count < GL->numVertexes){ // 如果输出的顶点个数小于图的顶点个数,则说明有环
        printf("图中有环");
    }
}

int main(){
    Graph G;
    createGraph(&G);
    Adj_List_Graph GL;
    createALGraph(&GL, G);
    printf("拓扑排序结果:\n");
    topologicalSort(GL);
    return 0;
}
